package chapter01;

import java.util.Arrays;

public class NextPermutation {
    //双指针
    //1 2 4 5 3
    //  i     j
    //外循环i的index从length-1~0
    //内循环j的index从length-1~i+1开始
    //找到num[i]<num[j]时交换两者 再对i+1~length-1从小到大排序
    public void nextPermutation(int[] nums) {
        if(nums.length<2){
            return;
        }
        int length=nums.length;
        for(int i=length-2;i>=0;i--){
            for(int j=length-1;j>i;j--){
                if(nums[i]<nums[j]){
                    nums[i]=nums[i]^nums[j];
                    nums[j]=nums[i]^nums[j];
                    nums[i]=nums[i]^nums[j];
                    Arrays.sort(nums,i+1,length);
                    return;
                }
            }
        }
        Arrays.sort(nums);
    }

    public static void main(String[] args) {
        int[] nums=new int[]{1,3,4,2};
        new NextPermutation().nextPermutation(nums);
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
    }
}
